package simple;

/**
 * 19:17 ~ 20:25 1小时8分钟
 * 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
 * 元素的 相对顺序 应该保持 一致 。
 *
 * 输入：nums = [0,0,1,1,1,2,2,3,3,4]
 * 输出：5, nums = [0,1,2,3,4]
 * 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
 *
 * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class RemoveDuplicatesFromSortedArray {
    public static void main(String[] args) {
        Solution1 solution = new Solution1();
        solution.removeDuplicates(new int[]{0,1,2});
    }
    /**
     * 移动数组元素的方式，最直接的方式。不太好 时间复杂度特别高
     * */
    static class Solution {
        public int removeDuplicates(int[] nums) {
            if(nums.length == 0){
                return 0;
            }
            int k = 0;
            // 新数组后的长度
            int length = nums.length;
            for (int i = k+1; i < length; i++) {
                if(nums[k] != nums[i]){
                    int a = i;
                    int b = k+1;
                    if(a > b){
                        while(a < length){
                            nums[b++] = nums[a++];
                        }
                    }
                    length -= a-b;
                    k++;
                    i = k;
                }
            }
            return Math.min(k+1,length);
        }
    }

    /**
     * 双指针的方式，一个指针a指向当前的位置，另外一个指针b去找到不等于指针a所指向的元素。
     * 当找到了，将b所指向的元素放到指针a指向的下标中
     * */
    static class Solution1{
        public int removeDuplicates(int[] nums) {
            int fast = 1;
            int slow = 1;
            while(fast < nums.length){
                if(nums[fast] != nums[fast-1]){
                    nums[slow] = nums[fast];
                    slow++;
                }
                fast++;
            }
            return slow;
        }
    }

    /**
     * 双指针方式2 这个更好理解
     * 这个方法有点跟我第一个方法的思路相似。
     * */
    static class Solution2{
        public int removeDuplicates(int[] nums) {
            int fast = 0;
            int slow = 0;
            while(fast < nums.length){
                if(nums[fast] == nums[slow]){
                    fast++;
                }else{
                    nums[++slow] = nums[fast];
                }
            }
            return slow+1;
        }
    }
}
